1. Field of the Invention
This invention relates to computer-based system which provides access to an image database by use of queries based on image characteristics.
2. Discussion of the Related Art
Relational databases which use queries to request retrieval of database information are well known. A query is a language-based request for information from a database based upon specific conditions. For example, a query may request a list of all bank customers whose account balances exceed a certain value.
A recent advance has freed the query function from language-based user operations. Tools are available in menu-driven dialog interfaces which enable a user to construct queries by manipulating icons in a dialog box on a display screen. The icons are arranged to symbolize database search requests.
To date, database systems which store images have not provided an efficient means of searching a database by other than textual attributes of the images. However, this requires the expenditure of significant resources to annotate images with text. Furthermore, limiting queries to textual annotations forgoes the possibility of searching an image database by using pixel information from the actual images which are stored in the database.
Much work has been expended to enable digital computers to recognize images by features which they contain. Some success has been achieved in having digital computers identify objects in images. H. Tamura, et al. have reported an advance in computational detection of image textures in their article entitled "Textural Features Corresponding to Visual Perception", IEEE Proceedings, Vol. SMC-8, No. 6, June 1978, pp. 460-473.
Similarly, for characterizing shape, various computational methods have been proposed. An example is the algebraic moment invariants of G. Taubin and D. B. Cooper "Recognition and Positioning of Rigid Objects Using Algebraic Moment Invariants", Geometric Methods in Computer Vision, SPIE Vol. 1570, pp. 175-186, 1992.
Several methods have been reported for querying computer image databases based on the colors and textures that occur in the images. The most common basis is color. Two cases occur. The first is when colors are selected by a user from a color wheel or other color picker, and images containing the selected colors are retrieved. An example of this is given in E. Binaghi, et al, "Indexing and Fuzzy Logic-Based Retrieval of Color Images", Visual Database Systems, II, IFIP Transactions A-7, pages 79-92, Elsevier Science Publishers, 1992, in which not only color but also percentage coverage of that color and compactness of its coverage are used as query conditions.
The second case is when a color image is specified, and similar images are to be retrieved. A method for doing this is described in M. J. Swain, et al, "Color Indexing", International Journal of Computer Vision, 7(1):11-32, 1991. The method uses "histogram intersection", in which a color histogram is computed for each image in the database, and a corresponding color histogram is computed for the query image. These histograms are computed over a quantized version of the available color space, giving, for example, 256 bins in the color histogram. A measure of similarity is defined for two histograms, and a query is run by computing the similarity between the query image histogram and the histogram of each image in the database.
A more sophisticated method for retrieving images similar to a given image is given in Mikihiro Ioka, "A Method of Defining the Similarity of Images on the Basis of Color Information", Technical Report RT-0030, IBM Tokyo Research Lab, 1989. Here, each image in the database (actually, the subimage of each image containing a single, dominant object in the image) is partitioned into blocks, for example, 25 blocks. Within each block, the reduced bucket histogram,h, (say, 256 buckets) is computed. Given a query image or object, it is also partitioned into the same number of blocks and the histograms computed. A similarity measure s(h.sub.query.sbsb.--.sub.image, h.sub.database.sbsb.--.sub.item) is defined on the color histograms computed in the blocks, and the measure is extended to images as: EQU S(query.sub.-- image, database.sub.-- image)=.SIGMA..sub.blocks s(h.sub.query.sbsb.--.sub.item, h.sub.database.sbsb.--.sub.item)
This method thus takes into account the distribution of colors in two images, as well as their spatial position, since the colors must not only match, but match at exactly the same positions to give a good matching score.